package leetcode_acm.leetcode_1;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月17日 12:08
 */
public class ReversePairs {
    private int[] memo;
    private int count = 0;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        memo = new int[n];
        sort(nums,0, nums.length-1);
        return count;
    }
    private void merge(int[] nums,int l,int mid,int r){
        for(int i = l;i <= r;i++){
            memo[i] = nums[i];
        }
        //此时左右两个部分都是有序的,只要比较即可
        int end = mid+1;
        for(int i = l;i <= r ;i++){
            while (end < r+1 && (long)nums[i] > (2L *nums[end])){
                end++;
            }
            //[mid+1,end) =>end -1 - mid -1 +1
            count += end-mid-1;
        }
        int i = l;int j = mid+1;
        for(int p = l;p <= r;p++){
            if(i == mid+1){
                nums[p] = memo[j++];
            }else if(j == r+1){
                nums[p] = memo[i++];
            }else if(memo[i] <= memo[j]){
                nums[p] = memo[i++];
            }else{
                nums[p] = memo[j++];
            }
        }
    }
    private void sort(int[] nums,int l,int r){
        if(l >= r){
            return ;
        }
        int mid = l+(l+(r-l)>>1);
        sort(nums,l,mid);
        sort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
}
